// $Id: heap.c 2 2011-10-17 17:49:43Z cedric.shih@gmail.com $
/*
 * Copyright 2011 Cedric Shih (cedric dot shih at gmail dot com)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>

#include "log.h"
#include "list.h"

#include "heap.h"

#define zcheap_lock(heap) do { \
	if (heap->lock && (errno = pthread_mutex_lock(heap->lock)) != 0) { \
		rc = errno; \
		zcbuffer_error("failed to lock: %s", strerror(rc)); \
		return rc; \
	} \
} while(0);

#define zcheap_unlock(heap) do { \
	if (heap->lock && (errno = pthread_mutex_unlock(heap->lock)) != 0) { \
		rc = errno; \
		zcbuffer_error("failed to unlock: %s", strerror(rc)); \
		return rc; \
	} \
} while(0);

int zcheap_add(struct zcheap *heap, struct zcbuffer *buffer, size_t len);

struct zcheap *zcheap_new(enum zcheap_type type,
		unsigned int capacity)
{
	struct zcheap *heap;

	zcbuffer_debug("constructing");

	if ((heap = calloc(1, sizeof(struct zcheap))) == NULL) {
		zcbuffer_error("failed to allocate memory");
		return NULL;
	}

	if ((heap->buffer = malloc(capacity * sizeof(u_char))) == NULL) {
		zcbuffer_error("failed to allocate heap: %d bytes", capacity);
		goto exception;
	}

	heap->offset = capacity;
	TAILQ_INIT(&heap->buffers);
	TAILQ_INIT(&heap->caches);

	heap->boundary = heap->buffer + heap->offset;
	heap->start = heap->buffer;

	return heap;

exception:
	zcheap_free(heap);
	return NULL;
}

void zcheap_clear_list(struct zcbuffer_list *list)
{
	int rc;
	struct zcbuffer_item *item;
	struct zcbuffer *buffer;

	while ((item = TAILQ_FIRST(list))) {
		buffer = item->buffer;
		if ((rc = zcbuffer_list_remove(list, item->buffer))) {
			zcbuffer_error("failed to remove: %s", strerror(rc));
			break;
		}
		free(buffer);
	}
}

void zcheap_free(struct zcheap *heap)
{
	if (heap == NULL) {
		return;
	}

	zcbuffer_debug("destructing");

	zcbuffer_debug("clearing buffers");

	zcbuffer_list_clear_caches(&heap->buffers);

	zcbuffer_debug("clearing caches");

	zcbuffer_list_clear_caches(&heap->caches);

	if (heap->buffer) {
		free(heap->buffer);
	}

	free(heap);
}

size_t zcheap_capacity(struct zcheap *heap)
{
	return heap->offset;
}

void zcheap_set_lock(struct zcheap *heap, pthread_mutex_t *lock)
{
	heap->lock = lock;
}

int zcheap_alloc_do(struct zcheap *heap, size_t len, struct zcbuffer **ptr)
{
	int rc;
	struct zcbuffer *buffer = NULL;

	zcheap_lock(heap);

	if (len > heap->offset) {
		zcbuffer_error("insufficient capacity: %d < %d",
				heap->offset, len);
		rc = ENOMEM;
		goto finally;
	}

	zcbuffer_trace("allocating %d bytes from heap: %p", len, heap);

	if (TAILQ_EMPTY(&heap->caches)) {
		if ((rc = zcbuffer_list_add_cache(&heap->caches, &buffer))) {
			zcbuffer_error("failed to add cache: %s", strerror(rc));
			goto finally;
		}
	}

	buffer = TAILQ_FIRST(&heap->caches)->buffer;
	buffer->type = ZCBUFFER_ROTATED;

	if ((rc = zcbuffer_list_remove(&heap->caches, buffer))) {
		zcbuffer_error("failed to remove: %s", strerror(rc));
		goto finally;
	}

	if ((rc = zcheap_add(heap, buffer, len))) {
		zcbuffer_error("failed to add: %s", strerror(rc));
		goto finally;
	}

	buffer->limit = buffer->capacity = len;
	buffer->position = buffer->mark = 0;

	zcbuffer_trace("allocated: %p", buffer);
	*ptr = buffer;
	rc = 0;

finally:
	zcheap_unlock(heap);
	return rc;
}

struct zcbuffer *zcheap_alloc(struct zcheap *heap, size_t len)
{
	struct zcbuffer *buffer;

	if ((errno = zcheap_alloc_do(heap, len, &buffer))) {
		return NULL;
	}

	return buffer;
}

size_t zcheap_available(struct zcheap *heap)
{
	size_t heap_free;

	zcbuffer_trace("calculating available space");

	if (heap->stat.count == 0) {
		heap_free = heap->offset;
	} else if (heap->next <= heap->start) {
		heap_free = heap->start - heap->next;
	} else if (heap->start == heap->buffer) {
		heap_free = heap->boundary - heap->next;
	} else {
		heap_free = heap->start - heap->buffer;
	}

	zcbuffer_trace("available: %u bytes", heap_free);

	return heap_free;
}

int zcheap_spare(struct zcheap *heap)
{
	int rc;
	struct zcbuffer *buffer;
	struct zcbuffer_item *first, *next;

	if (!(first = TAILQ_FIRST(&heap->buffers))) {
		zcbuffer_error("nothing to remove");
		rc = ENOENT;
		goto finally;
	}

	zcbuffer_trace("removing first buffer: %p", first->buffer);

	if ((next = TAILQ_NEXT(first, entry))) {
		heap->start = next->buffer->data;
	} else {
		heap->start = heap->buffer;
	}

	buffer = first->buffer;

	zcbuffer_free(buffer);

	if (!TAILQ_EMPTY(&buffer->clones)) {
		rc = EINPROGRESS;
		zcbuffer_error("still in use");
		goto finally;
	}

	if ((rc = zcbuffer_list_remove(&heap->buffers, buffer))) {
		zcbuffer_error("failed to remove: %s", strerror(rc));
		goto finally;
	}

	if ((rc = zcbuffer_list_add(&heap->caches, buffer))) {
		zcbuffer_error("failed to add: %s", strerror(rc));
		goto finally;
	}

	heap->stat.count--;
	heap->stat.dropped++;

	zcbuffer_trace("released from first buffer: %p-%p (%u bytes)",
			buffer->data, (buffer->data + buffer->capacity - 1),
			buffer->capacity);
	rc = 0;

finally:
	return rc;
}

int zcheap_reset(struct zcheap *heap)
{
	int rc;
	struct zcbuffer *buffer;
	struct zcbuffer_item *item;

	zcheap_lock(heap);

	zcbuffer_trace("resetting heap");

	while ((item = TAILQ_FIRST(&heap->buffers))) {
		buffer = item->buffer;

		if ((rc = zcbuffer_list_remove(&heap->buffers, buffer))) {
			zcbuffer_error("failed to remove: %s", strerror(rc));
			goto finally;
		}

		if ((rc = zcbuffer_list_add(&heap->caches, buffer))) {
			zcbuffer_error("failed to add: %s", strerror(rc));
			goto finally;
		}
	}

	heap->stat.count = heap->stat.put = heap->stat.dropped = 0;
	heap->boundary = heap->buffer + heap->offset;
	heap->start = heap->next = heap->buffer;

	rc = 0;

finally:
	zcheap_unlock(heap);
	return rc;
}

int zcheap_stat(struct zcheap *heap,
		struct zcheap_stat *stat)
{
	int rc;

	zcheap_lock(heap);

	zcbuffer_trace("getting statistics");

	memcpy(stat, &heap->stat, sizeof(heap->stat));
	rc = 0;

	zcheap_unlock(heap);
	return rc;
}

int zcheap_add(struct zcheap *heap, struct zcbuffer *buffer, size_t len)
{
	int rc;

	while (zcheap_available(heap) < len) {
		if ((rc = zcheap_spare(heap)) != 0) {
			zcbuffer_error("failed to spare: %s", strerror(rc));
			goto finally;
		}
	}

	zcbuffer_trace("allocating %d bytes", len);

	if ((rc = zcbuffer_list_add(&heap->buffers, buffer))) {
		zcbuffer_error("failed to add: %s", strerror(rc));
		goto finally;
	}

	if (heap->stat.count == 0 ||
			heap->boundary - heap->next < len) {
		heap->next = heap->buffer;
	}

	buffer->type = ZCBUFFER_ROTATED;
	buffer->source.heap = heap;
	buffer->data = heap->next;

	zcbuffer_trace("allocated %p: %p-%p (%u bytes)", buffer,
			buffer->data, (buffer->data + buffer->capacity - 1),
			buffer->capacity);

	heap->stat.count++;
	heap->stat.put++;
	heap->next += len;

	zcbuffer_trace("count: %d", heap->stat.count);

	rc = 0;

finally:
	return rc;
}

int zcheap_realloc(struct zcheap *heap, struct zcbuffer *buffer, size_t len)
{
	int rc;
	struct zcbuffer_item *last;
	size_t offset, oldlen;
	unsigned char *array;

	zcheap_lock(heap);

	if (buffer->type != ZCBUFFER_ROTATED ||
			buffer->source.heap != heap) {
		zcbuffer_error("not created from this");
		rc = EINVAL;
		goto finally;
	}

	if (!(last = TAILQ_LAST(&heap->buffers, zcbuffer_list))) {
		zcbuffer_error("heap is empty");
		rc = ENODATA;
		goto finally;
	}

	if (last->buffer != buffer) {
		zcbuffer_error("only supported on last buffer");
		rc = EPERM;
		goto finally;
	}

	if (heap->offset < len) {
		rc = EOVERFLOW;
		zcbuffer_error("insufficient heap size: %d < %d",
				heap->offset, len);
		goto finally;
	}

	if (buffer->position > len) {
		rc = EOVERFLOW;
		zcbuffer_error("buffer overflows: %d > %d",
				buffer->position, len);
		goto finally;
	}

	zcbuffer_trace("reallocating %p: %d => %d", buffer,
			buffer->capacity, len);

	oldlen = buffer->capacity;
	array = buffer->data;

	if (buffer->capacity > len) {
		offset = buffer->capacity - len;
		heap->next -= offset;
	} else {
		while ((zcheap_available(heap) + buffer->capacity) < len) {
			if ((rc = zcheap_spare(heap)) != 0) {
				zcbuffer_error("failed to spare: %s",
						strerror(rc));
				goto finally;
			}
		}

		if (TAILQ_EMPTY(&heap->buffers)) { // we spared ourself!!
			if ((rc = zcheap_add(heap, buffer, len))) {
				zcbuffer_error("failed to add: %s",
						strerror(rc));
				goto finally;
			}

			memcpy(buffer->data, array, buffer->capacity);
		}
	}

	buffer->capacity = len;

	if (buffer->limit > len) {
		zcbuffer_trace("adjusting limit: %d => %d", buffer->limit, len);
		buffer->limit = len;
	}

	if (buffer->mark > len) {
		zcbuffer_trace("adjusting mark: %d => %d", buffer->mark, len);
		buffer->mark = len;
	}

	rc = 0;

finally:
	zcheap_unlock(heap);
	return rc;
}
